package com.demo.datastructure.queue;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @description: 通过队列实现滑动窗口
 * @author: ljr
 * @time: 2021/5/2 10:02
 */
public class SildingWindowQueue {

    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] results = new int[nums.length-k+1];
        Deque<Integer> deque = new LinkedList<Integer>();
        int length = 0;
        for(int i = 0; i < nums.length; i++){
            while (!deque.isEmpty() && nums[deque.getLast()] < nums[i]){
                deque.removeLast();
            }
            deque.addLast(i);

            if(deque.getFirst() <= i-k){
                deque.removeFirst();
            }

            if(i+1-k >= 0){
                results[length++] = nums[deque.getFirst()];
            }
        }
        return results;
    }

    public static void main(String[] args) {
        SildingWindowQueue sildingWindowQueue = new SildingWindowQueue();
        int[] nums = new int[]{7,2,4};
        int[] results = sildingWindowQueue.maxSlidingWindow(nums, 2);
        for(int num : results){
            System.out.println(num);
        }
    }
}
